package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 437. 路径总和III
 * @date 2025/2/23 23:05
 */
public class E437 {

    private int sum = 0;

    /**
     * 递归解法
     * @param root root
     * @param targetSum targetSum
     * @return 总路径数
     */
    public int pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return sum;
    }

    // 遍历每个节点，分别作为起点再遍历
    private void dfs(TreeNode root, int targetSum) {
        if (root == null)
            return;
        dfs(root, targetSum, root.val);
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
    }

    // 遍历每个节点，计算路径和，有正负数
    private void dfs(TreeNode root, int targetSum, long currSum) {
        if (root == null)return;
        currSum += root.val;
        if (currSum == targetSum) sum++;
        dfs(root.left, targetSum, currSum);
        dfs(root.right, targetSum, currSum);
    }
}
